/*
day333 
2020.7.26 
*/
#include<iostream>
#include<vector>
using namespace std;

 
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
    	int change=k%nums.size(); 
    	
        reverse(nums,0,nums.size()-change-1);
        reverse(nums,nums.size()-change,nums.size()-1);
        reverse(nums,0,nums.size()-1);
    }
    
    void reverse(vector<int> &nums,int l,int r)
    {
    	int tem=0;
    	while(l<r)
    	{
    		tem=nums[l];
    		nums[l]=nums[r];
    		nums[r]=tem;
    		l++;
    		r--;
		}
	}
};



class Solution1 {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();
        int count = 0;
        for (int start = 0; count < nums.size(); start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.size();
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }

    }
};



int main()
{
	return 0;
}
